package listbyorder.access001_100.test53;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/1 16:26
 */
public class Solution1 {

    // 求解最大子序和(简单的动态规划)
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int ans = nums[0];
        int cur_sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur_sum = Math.max(cur_sum + nums[i], nums[i]);
            ans = Math.max(ans, cur_sum);
        }
        return ans;
    }

    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
